<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>代码痕迹</title>
</head>

<style type="text/css">
  * {
    margin: 0;
    padding: 0;
  }

  body {
    overflow: hidden;
  }

  div {
    display: grid;
    justify-items: center;
    width: 100vw;
    height: 100vh;
  }

  textarea {
    width: 55%;
    height: 100%;
    color: blue;
    border: 2px solid skyblue;
  }
</style>
</head>

<body>
  <div>
    <textarea>
  class TreeNode {
    // 定义节点
    constructor(val = 0, left = null, right = null) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
  
  // 创建二叉树
  const createTree = arr => {
    let root = new TreeNode(arr[0]);
    let Nodes = [root];
    let [i, len] = [1, arr.length];
  
    for (let node of Nodes) {
      if (arr[i] !== null) {
        Nodes.push((node.left = new TreeNode(arr[i])));
      }
      i += 1;
      if (i === len) return root;
      if (arr[i] !== null) {
        Nodes.push((node.right = new TreeNode(arr[i])));
      }
      i += 1;
      if (i === len) return root;
    }
  };
  
  // 防抖
  (function () {
    function deonuce(fn, delay = 300) {
      let time = null;
      return function () {
        let _this = this;
        clearTimeout(time);
        time = setTimeout(() => {
          fn.apply(_this, arguments);
        }, delay);
      };
    }
  })();
  
  // 节流
  (function () {
    function throttle(fn) {
      let falg = null;
      return function () {
        if (falg) return;
        let _this = this;
        falg = setTimeout(() => {
          fn.apply(_this, arguments);
          falg = null;
        }, 500);
      };
    }
  })();
  
  // 深拷贝
  (function () {
    const isObj = val => typeof val === 'Object' && val !== null;
  
    function deepClone(obj) {
      const newObj = obj instanceof Array ? [] : {};
      for (const key in object) {
        const item = obj[key];
        newObj[key] = isObj(item) ? deepClone(item) : item;
      }
      return item;
    }
  
    function deepClone(obj) {
      let obj1 = JSON.stringify(obj);
      let obj2 = JSON.parse(obj1);
      return obj2;
    }
  })();
  
  // 手写intstanceof
  (function () {
    function myInstancenof(left, right) {
      if (typeof left != 'object' || left === null) return false;
      let leftPro = left.__proto__,
        rightPro = right.prototype;
      while (true) {
        if (leftPro === null) return false;
        if (leftPro === rightPro) return true;
        leftPro = leftPro.__proto__;
      }
    }
  })();
  
  // 手写call apply bind
  (function () {
    Function.prototype.myCall = function (context) {
      if (typeof this !== 'function') {
        throw new Error('type erroe');
      }
      context = Object(context) || window;
      const fn = Symbol;
      context[fn] = this;
      const args = [...arguments].splice(1);
      const res = context[fn](...args);
      delete context[fn];
      return res;
    };
  
    Function.prototype.myApply = function (context) {
      if (typeof this !== 'function') {
        throw new Error('type error');
      }
      context = Object(context) || window;
      const fn = Symbol();
      context[fn] = this;
      const args = [...arguments][1];
  
      const res = context[fn](...args);
      delete context[fn];
      return res;
    };
  
    Function.prototype.myBind = function (context) {
      if (typeof this !== 'function') {
        throw new Error('type error');
      }
      context = Object(context) || window;
      const args = [...arguments].splice(1);
      const self = this;
  
      return function Fn(...newArguments) {
        if (this instanceof Fn) {
          return new self(...args, ...newArguments);
        } else {
          return self.apply(context, [...args, ...newArguments]);
        }
      };
    };
  })();
  
  // 手写new
  (function () {
    function myNew(fn, ...args) {
      let newObj = Object.create(fn.prototype);
      let res = fn.call(newObj, ...args);
      return res && typeof res === 'object' ? res : newObj;
    }
  })();
  
  // 数组扁平化
  (function () {
    const flatDeep = arr => {
      return arr.reduce((res, cur) => {
        if (Array.isArray(cur)) {
          return [...res, ...flatDeep(cur)];
        } else {
          return [...res, cur];
        }
      }, []);
    };
  })();
  
  function Person(uname, age) {
    this.uname = uname;
    this.age = age;
  }
  function Son(uname, age) {
    Person.call(this, uname, age);
  }
  var son = new Son('zhang', 12);
  
  // 数组去重
  (function () {
    function unique(arr) {
      var obj = {};
      return arr.filter((item, index, arr) =>
        obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true)
      );
    }
    var arr = [1,1, 'true', 'true', true, true, 15, 15, false, false, 
    undefined, undefined, null, null, NaN, NaN, 'NaN', 0, 0, 'a', 'a', {}, {}];
  })();
  
  var a = [1, 2, 3, 4, 5];
  var b = [2, 4, 6, 8, 10];
  //交集
  var c = a.filter(item => b.indexOf(item) > -1);
  //差集
  var d = a.filter(item => b.indexOf(item) == -1);
  //补集
  var e = a.filter(item => !(b.indexOf(item) > -1)).concat(b.filter(item => !(a.indexOf(item) > -1)));
  //并集
  var f = a.concat(b.filter(item => !(a.indexOf(item) > -1)));
  
  a1 = [1, 2, 12];
  a2 = [4, 23];
  a1.concat(a2);
  
  a1.sort();
  
  (function () {
    var s = 'bxj###tw',
      t = 'bxj##tw';
  
    var backspaceCompare = function (s, t) {
      return back(s) === back(t);
    };
    let back = str => {
      let [res, num] = ['', 0];
      for (let i = str.length - 1; i >= 0; i--) {
        if (str[i] === '#') {
          num++;
        } else if (num > 0) {
          num--;
        } else {
          res += str[i];
        }
      }
      return res;
    };
  })();
  
  (function () {
    var findAnagrams = function (s, p) {
      const res = [];
      let count = new Array(26).fill(0);
      for (let i = 0; i < p.length; i++) {
        count[p.charCodeAt(i) - 'a'.charCodeAt()]++;
        count[s.charCodeAt(i) - 'a'.charCodeAt()]--;
      }
      if (allZero(count)) res.push(0);
      for (let i = p.length; i < s.length; i++) {
        count[s.charCodeAt(i) - 'a'.charCodeAt()]--;
        count[s.charCodeAt(i - p.length) - 'a'.charCodeAt()]++;
        if (allZero(count)) res.push(i - p.length + 1);
      }
      return res;
    };
    function allZero(count) {
      for (const item of count) {
        if (item != 0) return false;
      }
      return true;
    }
  })();
  
  (function () {
    var connect = function (root) {
      if (!root) return null;
      const qu = [root];
      while (qu.length) {
        const len = qu.length;
        let last = null;
        for (let i = 1; i <= len; i++) {
          let f = qu.shift();
          if (f.left != null) {
            qu.push(f.left);
          }
          if (f.right != null) {
            qu.push(f.right);
          }
          if (i != 1) {
            last.next = f;
          }
          last = f;
        }
      }
      return root;
    };
  })();
  
  // 重排链表
  (function () {
    const getMid = head => {
      let [slow, fast] = [head, head];
      while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
      }
      return slow;
    };
  
    const merge = (l1, l2) => {
      while (l1 && l2) {
        let [n1, n2] = [l1.next, l2.next];
        l1.next = l2;
        l2.next = n1;
        l1 = n1;
        l2 = n2;
      }
    };
  
    var reorderList = function (head) {
      let mid = getMid(head);
      let next = reverse(mid.next);
      mid.next = null;
      merge(head, next);
    };
  
    const reverse = head => {
      let [cur, pre] = [head, null];
      while (cur) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
      }
      return pre;
    };
  })();
  
  // 用栈实现队列 143
  (function () {
    var MyQueue = function () {
      this.stack1 = [];
      this.stack2 = [];
    };
  
    /**
     * @param {number} x
     * @return {void}
     */
    MyQueue.prototype.push = function (x) {
      this.stack1.push(x);
    };
  
    /**
     * @return {number}
     */
    MyQueue.prototype.pop = function () {
      if (this.stack2.length > 0) {
        return this.stack2.pop();
      }
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      }
      return this.stack2.pop();
    };
  
    /**
     * @return {number}
     */
    MyQueue.prototype.peek = function () {
      let temp = this.pop();
      this.stack2.push(temp);
      return temp;
    };
  
    /**
     * @return {boolean}
     */
    MyQueue.prototype.empty = function () {
      return this.stack1.length === 0 && this.stack2.length === 0;
    };
  
    /**
     * Your MyQueue object will be instantiated and called as such:
     * var obj = new MyQueue()
     * obj.push(x)
     * var param_2 = obj.pop()
     * var param_3 = obj.peek()
     * var param_4 = obj.empty()
     */
  })();
  
  // 二叉树的右视图 199
  (function () {
    var rightSideView = function (root) {
      if (root.val == null) return [];
      const res = [root.val];
      while (root.right) {
        root = root.right;
        res.push(root.val);
      }
      return res;
    };
  })();
  
  //算术平方根
  var mySqrt = function (x) {
    let [left, right] = [0, x];
    if (x === 0 || x === 1) return x;
    while (right - left !== 1) {
      let mid = (right + left) >> 1;
      let temp = mid * mid;
      if (temp === x) {
        return mid;
      } else if (temp > x) {
        right = mid;
      } else {
        left = mid;
      }
    }
    return left;
  };
  
  // 31.下一个排列
  (function () {
    let nums = [1, 5];
    var nextPermutation = function (nums) {
      let [len, index] = [nums.length - 1, 0];
      let idx = len;
  
      for (let i = 0; i < len; i++) {
        if (nums[i] <= nums[i + 1]) {
          index = i + 1;
          break;
        }
      }
      if (index <= 0) {
        return nums.reverse();
      } else {
        while (nums[idx] <= nums[index]) {
          idx--;
        }
        let temp = nums[index];
        nums[index] = nums[idx];
        nums[idx] = temp;
        // [nums[index], nums[idx]] = [nums[idx], nums[index]]
      }
  
      return nums;
    };
    nextPermutation(nums);
  })();
  
  //  Z 字形变换
  (function () {
    var s = 'PAYPALISHIRIN',
      numRows = 3;
    var convert = function (s, numRows) {
      if (numRows === 1) return s;
      let rows = new Array(numRows).fill('');
      let [isDowm, loc] = [false, 0];
      for (const c of s) {
        rows[loc] += c;
        if (loc === 0 || loc === numRows - 1) isDowm = !isDowm;
        loc += isDowm ? 1 : -1;
      }
      return rows.join('');
    };
  })();
  
  // 寻找旋转排序数组中的最小值
  (function () {
    var nums = [1];
    var findMin = function (nums) {
      let [left, right, mid] = [0, nums.length - 1, 0];
      if (nums[left] <= nums[right]) return nums[left];
      while (left <= right) {
        mid = (left + right) >> 1;
        if (nums[mid] > nums[mid + 1]) {
          return nums[mid + 1];
        } else if (nums[mid] < nums[left]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      }
    };
  })();
  
  // 162. 寻找峰值
  (function () {
    var findPeakElement = function (nums) {
      let left = 0,
        right = nums.length - 1;
      while (left < right) {
        let mid = Math.ceil((left + right) / 2);
        if (nums[mid - 1] > nums[mid]) right = mid - 1;
        else left = mid;
      }
      return left;
    };
  })();
  
  (function () {
    let n = 5;
    let arrSeven = [-6, 0, 2, -2, 3];
    const turnSeven = (n, arrSeven) => {
      let [res, sev, len] = [0, 0, n - 1];
      arrSeven.sort((a, b) => a - b);
      sev = Math.abs(arrSeven[0]) > Math.abs(arrSeven[len]) ? arrSeven[0] : arrSeven[len];
      if (sev < 0) {
        // 绝对值最大
        res += Math.abs(7 - Math.abs(arrSeven[0]));
        res += Math.abs(Math.abs(arrSeven[1]) - 1);
        for (let i = 2; i <= len; i++) {
          res += Math.abs(Math.abs(arrSeven[i]) - 1);
        }
      } else {
        res += Math.abs(7 - arrSeven[len]);
        for (let i = 0; i < len; i++) {
          res += Math.abs(Math.abs(arrSeven[i]) - 1);
        }
      }
      return res;
    };
  })();
  
  // 7. 整数反转
  (function () {
    var reverse = function (x) {
      let res = '';
      if (x < 0) {
        res = -Math.abs(x).toString().split('').reverse().join('');
      } else {
        res = Math.abs(x).toString().split('').reverse().join('');
      }
      if (res >= Math.pow(2, 31) - 1 || res <= Math.pow(-2, 31)) res = 0;
      return res;
    };
  })();
  
  // 删除排序链表中的重复元素 II
  (function () {
    function ListNode(val, next) {
      this.val = val === undefined ? 0 : val;
      this.next = next === undefined ? null : next;
    }
    var deleteDuplicates = function (head) {
      if (!head) return head;
      let dummy = new ListNode(-1, head);
      let [left, right] = [dummy, head];
      while (right) {
        while (right.next && right.next.val === right.val) {
          right = right.next;
        }
        if (left.next === right) left = left.next;
        else left.next = right.next;
        right = right.next;
      }
      return dummy.next;
    };
  })();
  
  (function () {
    function arrayNonRepeatfy(arr) {
      let map = new Map();
      let array = new Array(); // 数组用于返回结果
      for (let i = 0; i < arr.length; i++) {
        if (map.has(arr[i])) {
          // 如果有该key值
          map.set(arr[i], true);
        } else {
          map.set(arr[i], false); // 如果没有该key值
          array.push(arr[i]);
        }
      }
      return array;
    }
    var arr = [
      1,
      1,
      'true',
      'true',
      true,
      true,
      15,
      15,
      false,
      false,
      undefined,
      undefined,
      null,
      null,
      NaN,
      NaN,
      'NaN',
      0,
      0,
      'a',
      'a',
      {},
      {}
    ];
  })();
  
  // 986. 区间列表的交集
  (function () {
    let firstList = [
        [0, 2],
        [5, 10],
        [13, 23],
        [24, 25]
      ],
      secondList = [
        [1, 5],
        [8, 12],
        [15, 24],
        [25, 26]
      ];
    var intervalIntersection = function (firstList, secondList) {
      let i = (j = 0);
      const res = [];
      while (i < firstList.length && j < secondList.length) {
        let left = (right = 0);
        left = Math.max(firstList[i][0], secondList[j][0]);
        right = Math.min(firstList[i][1], secondList[j][1]);
        if (left <= right) {
          res.push([left, right]);
        }
        firstList[i][1] < secondList[j][1] ? i++ : j++;
      }
      return res;
    };
  })();
  
  // 547. 省份数量
  (function () {
    let isConnected = [
      [1, 1, 0],
      [1, 1, 0],
      [0, 0, 1]
    ];
  
    const dfs = (isConnected, arr, len, i) => {
      for (let j = 0; j < len; j++) {
        if (isConnected[i][j] === 1 && !arr.has(j)) {
          arr.add(i);
          dfs(isConnected, arr, len, j);
        }
      }
    };
  
    var findCircleNum = function (isConnected) {
      const len = isConnected.length;
      const arr = new Set();
      let res = 0;
      for (let i = 0; i < isConnected.length; i++) {
        if (!arr.has(i)) {
          dfs(isConnected, arr, len, i);
          res++;
        }
      }
      return res;
    };
  })();
  // 139. 单词拆分
  (function () {
    let s = 'applepenapple',
      wordDict = ['apple', 'pen'];
  
    var wordBreak = function (s, wordDict) {
      const len = s.length;
      const set = new Set(wordDict);
      let arr = new Array(n + 1).fill(false);
      arr[0] = true;
      for (let i = 0; i <= len; i++) {
        for (let j = 0; j < i; j++) {
          if (arr[j] && set.has(s.substr(j, i - j))) {
            arr[i] = true;
            break;
          }
        }
      }
      return arr[len];
    };
  })();
  
  // 91. 解码方法
  (function () {
    let s = '12';
    var numDecodings = function (s) {
      const len = s.length;
      // const arr = new Array(len + 1).fill(0)
      // arr[0] = 1
      let [a, b, c] = [0, 1, 0];
      for (let i = 1; i <= len; i++) {
        c = 0;
        if (s[i - 1] !== '0') {
          c += b;
        }
        if (i > 1 && s[i - 2] !== '0' && (s[i - 2] - '0') * 10 + (s[i - 1] - '0') < 27) {
          c += a;
        }
        [a, b] = [b, c];
      }
      // return arr[len]
      return c;
    };
  })();
  
  // 300. 最长递增子序列
  (function () {
    let nums = [1, 3, 6, 7, 9, 4, 10, 5, 6];
    var lengthOfLIS = function (nums) {
      const len = nums.length;
      if (len < 2) return len;
  
      const arr = new Array(len).fill(1);
      for (let i = 0; i < len; i++) {
        for (let j = 0; j < i; j++) {
          if (nums[i] > nums[j]) {
            arr[i] = Math.max(arr[i], arr[j] + 1);
          }
        }
      }
      return Math.max(...arr);
    };
  })();
  
  // 673. 最长递增子序列的个数
  (function () {
    let nums = [1, 3, 5, 4, 7];
    // let nums = [2, 2, 2, 2, 2]
    var findNumberOfLIS = function (nums) {
      // dp[i] 表示nums[i]结尾的最长子序列的长度
      // cnt[i] 表示nums[i]结尾的 最长递增子序列的种类个数
      let dp = new Array(nums.length).fill(1);
      let cnt = new Array(nums.length).fill(1);
      for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
          if (nums[i] > nums[j]) {
            if (dp[j] + 1 > dp[i]) {
              // 找到了一个更长的递增子序列.
              dp[i] = dp[j] + 1;
              cnt[i] = cnt[j]; // 长度增加了 种类不会增加 继承原来的cnt
            } else if (dp[j] + 1 === dp[i]) {
              // 找到了两个相同长度的递增子序列.
              cnt[i] += cnt[j]; // 长度虽然没变 但种类增加了， cnt+=
            }
          }
        }
      }
      let res = 0;
      let max = Math.max(...dp); // 最长有多长 max记录一下
      for (let i = 0; i < dp.length; i++) {
        if (dp[i] === max) res += cnt[i]; // dp中所有最长的 对应cnt 累加
      }
      return res;
    };
  })();
  
  // 1143. 最长公共子序列
  (function () {
    let text1 = 'abcde',
      text2 = 'ace';
    var longestCommonSubsequence = function (text1, text2) {
      let [m, n] = [text1.length, text2.length];
      let dp = Array.from(Array(m + 1), () => Array.from(n + 1).fill(0));
      for (let i = 1; i < m + 1; i++) {
        for (let j = 1; j < n + 1; j++) {
          if (text1[i - 1] === text2[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1];
          } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
          }
        }
      }
  
      return dp[m][n];
    };
  })();
  
  // 两数相加
  (function () {
    var addTwoNumbers = function (l1, l2) {
      const stack1 = [],
        stack2 = [];
      let carry = 0;
      let node = new ListNode(),
        cur = node,
        head = null;
      while (l1) {
        stack1.push(l1.val);
        l1 = l1.next;
      }
      while (l2) {
        stack2.push(l2.val);
        l2 = l2.next;
      }
      while (stack1.length || stack2.length || carry) {
        let val1 = stack1.length ? stack1.shift() : 0;
        let val2 = stack2.length ? stack2.shift() : 0;
        let sum = val1 + val2 + carry;
        cur.next = new ListNode(sum % 10);
        cur = cur.next;
        carry = Math.floor(sum / 10);
      }
      return node.next;
    };
  })();
  
  // 两数相加II
  (function () {
    var addTwoNumbers = function (l1, l2) {
      const stack1 = [],
        stack2 = [];
      let carry = 0;
      let head = null;
      while (l1) {
        stack1.push(l1.val);
        l1 = l1.next;
      }
      while (l2) {
        stack2.push(l2.val);
        l2 = l2.next;
      }
      while (stack1.length || stack2.length || carry) {
        let val1 = stack1.length ? stack1.pop() : 0;
        let val2 = stack2.length ? stack2.pop() : 0;
        let sum = val1 + val2 + carry;
        carry = Math.floor(sum / 10);
        let node = new ListNode(sum % 10);
        node.next = head;
        head = node;
      }
      return head;
    };
  })();
  
  // 8. 字符串转换整数 (atoi)
  (function () {
    let s = ' 987';
    var myAtoi = function (str) {
      //利用正则
      let result = str.trim().match(/^[-+]?\d+/);
      if (result != null) {
        if (result[0] > Math.pow(2, 31) - 1) {
          return Math.pow(2, 31) - 1;
        }
        if (result[0] < Math.pow(-2, 31)) {
          return Math.pow(-2, 31);
        }
  
        return result[0];
      }
  
      return 0;
    };
  })();
  
  // 43. 字符串相乘
  (function () {
    let num1 = 1,
      num2 = '3';
    var multiply = function (num1, num2) {
      return num1.charCodeAt();
    };
  })();
  
  // 38.组合总和
  (function () {
    var combinationSum = function (candidates, target) {
      const [res, len] = [[], candidates.length];
  
      const dfs = (path, total, startIndex) => {
        if (total > target) return;
        if (total === target) {
          res.push([...path]);
        }
  
        for (let i = startIndex; i < len; i++) {
          path.push(candidates[i]);
          total += candidates[i];
          dfs(path, total, i);
          total -= candidates[i];
          path.pop();
        }
      };
      dfs([], 0, 0);
      return res;
    };
  })();
  
  // 27. 移除元素
  (function () {
    let nums = [0, 1, 2, 2, 3, 0, 4, 2],
      val = 2;
    var removeElement = function (nums, val) {
      let slow = 0;
  
      for (let fast = 0; fast < nums.length; fast++) {
        if (nums[fast] !== val) {
          nums[slow++] = nums[fast];
        }
      }
      return slow;
    };
    removeElement(nums, val);
  })();
  
  // 977. 有序数组的平方
  (function () {
    let nums = [-4, -1, 0, 3, 10];
    var sortedSquares = function (nums) {
      let len = nums.length - 1;
      let [left, right] = [0, len];
      const res = new Array(len + 1).fill(0);
  
      while (left <= right) {
        let leftTwo = nums[left] * nums[left];
        let rightTwo = nums[right] * nums[right];
        if (leftTwo < rightTwo) {
          res[len--] = rightTwo;
          right--;
        } else {
          res[len--] = leftTwo;
          left++;
        }
      }
      return res;
    };
    sortedSquares(nums);
  })();
  
  // 209. 长度最小的子数组
  (function () {
    let target = 7,
      nums = [2, 3, 1, 2, 4, 3];
    var minSubArrayLen = function (target, nums) {
      let [left, sum, len] = [0, 0, nums.length];
      let res = len + 1;
      for (let right = 0; right < len; right++) {
        sum += nums[right];
        while (sum >= target) {
          let temp = right - left + 1;
          res = res < temp ? res : temp;
          sum -= nums[left++];
        }
      }
      return res === len + 1 ? 0 : res;
    };
    minSubArrayLen(target, nums);
  })();
  
  // 59. 螺旋矩阵 II
  (function () {
    let n = 3;
    var generateMatrix = function (n) {
      let [startX, startY, offset, count] = [0, 0, 1, 1];
      let arr = new Array(n).fill().map(() => new Array(n));
      let turnIndex = n / 2;
  
      while (turnIndex > 0) {
        let [x, y] = [startX, startY];
        while (y < n - offset) {
          arr[startX][y++] = count++;
        }
        while (x < n - offset) {
          arr[x++][y] = count++;
        }
        while (y > startX) {
          arr[x][y--] = count++;
        }
        while (x > startY) {
          arr[x--][y] = count++;
        }
        offset++;
        startX++;
        startY++;
        turnIndex--;
      }
      if (n & 1) {
        arr[startX - 1][startY - 1] = count;
      }
      return arr;
    };
    generateMatrix(n);
  })();
  
  // 203. 移除链表元素
  (function () {
    function ListNode(val, next) {
      this.val = val === undefined ? 0 : val;
      this.next = next === undefined ? null : next;
    }
    var removeElements = function (head, val) {
      let dummy = new ListNode();
      dummy.next = head;
      let cur = dummy;
      while (cur.next) {
        if (cur.next.val === val) {
          cur.next = cur.next.next;
        } else {
          cur = cur.next;
        }
      }
      return dummy.next;
    };
  })();
  
  // 206. 反转链表
  (function () {
    var reverseList = function (head) {
      const listReverse = (cur, pre) => {
        if (!pre) return pre;
        let temp = cur.next;
        cur.next = pre;
        listReverse(temp, cur);
      };
      return reverseList(head, null);
    };
  })();
  
  // 24. 两两交换链表中的节点
  (function () {
    var swapPairs = function (head) {
      let dummy = new ListNode(0);
      let cur = dummy;
      dummy.next = head;
      while (cur.next && cur.next.next) {
        let temp = cur.next;
        let temp1 = cur.next.next;
        cur.next = cur.next.next;
        cur.next.next = temp;
        temp.next = temp1;
        cur = cur.next.next;
      }
      return dummy.next;
    };
  })();
  
  // 19. 删除链表的倒数第 N 个结点
  (function () {
    var removeNthFromEnd = function (head, n) {
      let dummy = new ListNode(0, head);
      let fast = (slow = dummy);
      n++;
      while (n-- >= 0 && fast) {
        fast = fast.next;
      }
      while (fast) {
        fast = fast.next;
        slow = slow.next;
      }
      slow.next = slow.next.next;
      return dummy;
    };
  })();
  
  // 142. 环形链表 II
  (function () {
    var detectCycle = function (head) {
      if (!head || !head.next) return null;
      let fast = (slow = head);
  
      while (fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) {
          let index = fast;
          let index2 = head;
          while (index !== index2) {
            index = index.next;
            index2 = index2.next;
          }
          return index;
        }
      }
      return null;
    };
  })();
  
  // 242. 有效的字母异位词
  (function () {
    let s = 'rat',
      t = 'cat';
    var isAnagram = function (s, t) {
      const [len1, len2] = [s.length, t.length];
      if (len1 !== len2) return false;
      const hash = new Array(26).fill(0);
      for (let i = 0; i < len1; i++) {
        hash[s[i].charCodeAt() - 'a'.charCodeAt()]++;
      }
  
      for (let i = 0; i < len2; i++) {
        hash[t[i].charCodeAt() - 'a'.charCodeAt()]--;
      }
  
      for (const item of hash) {
        if (item !== 0) return false;
      }
      return true;
    };
    isAnagram(s, t);
  })();
  
  // 1. 两数之和
  (function () {
    let nums = [2, 7, 11, 15],
      target = 9;
    var twoSum = function (nums, target) {
      const hash = new Map();
      for (let i = 0; i < nums.length; i++) {
        let temp = target - nums[i];
        if (hash.has(temp)) {
          return [hash.get(temp), i];
        }
        hash.set(nums[i], i);
      }
      return [];
    };
  })();
  
  // 454. 四数相加 II
  (function () {
    var fourSumCount = function (nums1, nums2, nums3, nums4) {
      let arr = new Map();
      let res;
  
      for (let x = 0; x < nums1.length; x++) {
        for (let y = 0; y < nums2.length; y++) {
          const sum = nums1[x] + nums2[y];
          arr.set(sum, (arr.get(sum) || 0) + 1);
        }
      }
  
      for (let x = 0; x < nums3.length; x++) {
        for (let y = 0; y < nums4.length; y++) {
          const target = 0 - nums3[x] + nums4[y];
          if (arr.has(target)) {
            res += arr.get(0 - target) || 0;
          }
        }
      }
  
      return res;
    };
  })();
  
  // 18. 四数之和
  (function () {
    let nums = [1, 0, -1, 0, -2, 2],
      target = 0;
    var fourSum = function (nums, target) {
      const len = nums.length;
      if (len < 4) return [];
      nums.sort((a, b) => a - b);
      const res = [];
      for (let i = 0; i < len - 3; i++) {
        // 去重i
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        for (let j = i + 1; j < len - 2; j++) {
          // 去重j
          if (j > i + 1 && nums[j] === nums[j - 1]) continue;
          let l = j + 1,
            r = len - 1;
          while (l < r) {
            const sum = nums[i] + nums[j] + nums[l] + nums[r];
            if (sum < target) {
              l++;
              continue;
            }
            if (sum > target) {
              r--;
              continue;
            }
            res.push([nums[i], nums[j], nums[l], nums[r]]);
  
            // 对nums[left]和nums[right]去重
            while (l < r && nums[l] === nums[++l]);
            while (l < r && nums[r] === nums[--r]);
          }
        }
      }
      return res;
    };
  })();
  
  // 344. 反转字符串
  (function () {
    let s = ['h', 'e', 'l', 'l', 'o'];
    var reverseString = function (s) {
      let len = s.length;
      for (let i = 0, j = len - 1; i < len / 2; i++, j--) {
        [s[i], s[j]] = [s[j], s[i]];
      }
      return s;
    };
  })();
  
  // 541. 反转字符串 II
  (function () {
    let s = 'abcdefg',
      k = 2;
    var reverseStr = function (s, k) {
      const len = s.length;
      let res = s.split('');
      for (let i = 0; i < len; i += 2 * k) {
        let left = i,
          right = i + k > len ? len : i + k;
        while (left < --right) [res[left++], res[right]] = [res[right], res[left]];
      }
      return res.join('');
    };
  })();
  
  // 151. 反转字符串中的单词
  (function () {
    let s = '  hello   world  ';
    const removeExtraSpaces = strArr => {
      let [fast, slow] = [0, 0];
  
      while (fast < strArr.length) {
        if (strArr[fast] === ' ' && (fast === 0 || strArr[fast - 1] === ' ')) {
          fast++;
        } else {
          strArr[slow++] = strArr[fast++];
        }
      }
  
      strArr.length = strArr[slow - 1] === ' ' ? slow - 1 : slow;
    };
  
    const reverse = (strArr, start, end) => {
      let [left, right] = [start, end];
      while (left < right) {
        [strArr[left++], strArr[right--]] = [strArr[right], strArr[left]];
      }
    };
  
    var reverseWords = function (s) {
      const strArr = Array.from(s);
  
      removeExtraSpaces(strArr);
  
      reverse(strArr, 0, strArr.length - 1);
  
      let start = 0;
  
      for (let i = 0; i <= strArr.length; i++) {
        if (strArr[i] === ' ' || i === strArr.length) {
          reverse(strArr, start, i - 1);
          start = i + 1;
        }
      }
      return strArr.join('');
    };
  })();
  
  // KMP算获得next数组
  (function () {
    let str = 'aabaaf';
    const getNextArr = s => {
      let next = [],
        j = 0;
      next[0] = 0;
      for (let i = 1; i < s.length; i++) {
        while (j > 0 && s[i] !== s[j]) {
          j = next[j - 1];
        }
        if (s[i] === s[j]) j++;
        next[i] = j;
      }
      return next;
    };
  })();
  
  // 459. 重复的子字符串
  (function () {
    let s = 'abac';
    var repeatedSubstringPattern = function (s) {
      const getKmp = s => {
        let j = 0,
          next = [];
        next[0] = 0;
        for (let i = 1; i < s.length; i++) {
          while (j > 0 && s[i] !== s[j]) {
            j = next[j - 1];
          }
          if (s[i] === s[j]) j++;
          next[i] = j;
        }
        return next;
      };
  
      let next = getKmp(s);
      const len = s.length;
      let max = len - next[next.length - 1];
  
      if (len % max === 0 && max !== len1) {
        return true;
      } else {
        return false;
      }
    };
  })();
  
  // 225. 用队列实现栈
  (function () {
    var MyStack = function () {
      this.queue = [];
    };
  
    /**
     * @param {number} x
     * @return {void}
     */
    MyStack.prototype.push = function (x) {
      this.queue.push(x);
    };
  
    /**
     * @return {number}
     */
    MyStack.prototype.pop = function () {
      let len = this.queue.length;
      while (len-- > 1) {
        this.queue.push(this.queue.shift());
      }
      return this.queue.shift();
    };
  
    /**
     * @return {number}
     */
    MyStack.prototype.top = function () {
      const temp = this.pop();
      this.queue.push(temp);
      return temp;
    };
  
    /**
     * @return {boolean}
     */
    MyStack.prototype.empty = function () {
      return !this.queue.length;
    };
  
    /**
     * Your MyStack object will be instantiated and called as such:
     * var obj = new MyStack()
     * obj.push(x)
     * var param_2 = obj.pop()
     * var param_3 = obj.top()
     * var param_4 = obj.empty()
     */
  })();
  
  //20. 有效的括号
  (function () {
    let s = '([])';
    var isValid = function (s) {
      const len = s.length;
      if ((len & 1) !== 0) return false;
      const stack = [];
      for (let i = 0; i < len; i++) {
        if (s[i] === '(') {
          stack.unshift(')');
        } else if (s[i] === '[') {
          stack.unshift(']');
        } else if (s[i] === '{') {
          stack.unshift('}');
        } else if (stack.length === 0 || stack.shift() !== s[i]) {
          return false;
        }
      }
      return stack.length === 0;
    };
  })();
  
  // 1047. 删除字符串中的所有相邻重复项
  (function () {
    let s = 'abbaca';
    var removeDuplicates = function (s) {
      const stack = [];
      for (const item of s) {
        let temp = null;
        if (stack.length === 0 || (temp = stack.pop()) !== item) {
          temp && stack.push(temp);
          stack.push(item);
        }
      }
      return stack.join('');
    };
  })();
  
  // 150. 逆波兰表达式求值
  (function () {
    const tokens = ['2', '1', '+', '3', '*'];
    var evalRPN = function (tokens) {
      const symbol = new Map([
        ['+', (a, b) => b + a],
        ['-', (a, b) => b - a],
        ['*', (a, b) => b * a],
        ['/', (a, b) => (b / a) | 0]
      ]);
      const res = [];
      for (const item of tokens) {
        if (!symbol.has(item)) {
          res.unshift(item - 0);
          continue;
        }
        res.unshift(symbol.get(item)(res.shift(), res.shift()));
      }
      return res.shift();
    };
  })();
  
  // 239. 滑动窗口最大值
  (function () {
    let nums = [1, 3, 1, 2, 0, 5],
      k = 3;
    var maxSlidingWindow = function (nums, k) {
      class MonoQueue {
        queue;
        constructor() {
          this.queue = [];
        }
  
        enqueue(val) {
          let back = this.queue[this.queue.length - 1];
          while (back !== undefined && back < val) {
            this.queue.pop();
            back = this.queue[this.queue.length - 1];
          }
          this.queue.push(val);
        }
  
        dequeue(val) {
          let front = this.front();
          if (front === val) {
            this.queue.shift();
          }
        }
  
        front() {
          return this.queue[0];
        }
      }
  
      let helperQueue = new MonoQueue();
      let i = 0,
        j = 0;
      let res = [];
      while (j < k) {
        helperQueue.enqueue(nums[j++]);
      }
      res.push(helperQueue.front());
      while (j < nums.length) {
        helperQueue.enqueue(nums[j]);
        helperQueue.dequeue(nums[i]);
        res.push(helperQueue.front());
        i++;
        j++;
      }
      return res;
    };
  })();
  
  // 347. 前 K 个高频元素
  (function () {
    // js 没有堆 需要自己构造
    class Heap {
      constructor(compareFn) {
        this.compareFn = compareFn;
        this.queue = [];
      }
  
      // 使用传入的 compareFn 比较两个位置的元素
      compare(index1, index2) {
        // 处理下标越界问题
        if (this.queue[index1] === undefined) return 1;
        if (this.queue[index2] === undefined) return -1;
  
        return this.compareFn(this.queue[index1], this.queue[index2]);
      }
  
      // 添加
      push(item) {
        // 推入元素
        this.queue.push(item);
  
        // 上浮
        let index = this.size() - 1; // 记录推入元素下标
        let parent = Math.floor((index - 1) / 2); // 记录父节点下标
  
        while (parent >= 0 && this.compare(parent, index) > 0) {
          // 注意compare参数顺序
          [this.queue[index], this.queue[parent]] = [this.queue[parent], this.queue[index]];
  
          // 更新下标
          index = parent;
          parent = Math.floor((index - 1) / 2);
        }
      }
  
      // 获取堆顶元素并移除
      pop() {
        // 堆顶元素
        const out = this.queue[0];
  
        // 移除堆顶元素 填入最后一个元素
        this.queue[0] = this.queue.pop();
  
        // 下沉
        let index = 0; // 记录下沉元素下标
        let left = 1; // left 是左子节点下标 left + 1 则是右子节点下标
        let searchChild = this.compare(left, left + 1) > 0 ? left + 1 : left;
  
        while (searchChild !== undefined && this.compare(index, searchChild) > 0) {
          // 注意compare参数顺序
          [this.queue[index], this.queue[searchChild]] = [this.queue[searchChild], this.queue[index]];
  
          // 更新下标
          index = searchChild;
          left = 2 * index + 1;
          searchChild = this.compare(left, left + 1) > 0 ? left + 1 : left;
        }
  
        return out;
      }
  
      size() {
        return this.queue.length;
      }
    }
  
    const topKFrequent = function (nums, k) {
      const map = new Map();
  
      for (const num of nums) {
        map.set(num, (map.get(num) || 0) + 1);
      }
  
      // 创建小顶堆
      const heap = new Heap((a, b) => a[1] - b[1]);
  
      // entry 是一个长度为2的数组，0位置存储key，1位置存储value
      for (const entry of map.entries()) {
        heap.push(entry);
  
        if (heap.size() > k) {
          heap.pop();
        }
      }
  
      // return heap.queue.map(e => e[0]);
  
      const res = [];
  
      for (let i = heap.size() - 1; i >= 0; i--) {
        res[i] = heap.pop()[0];
      }
  
      return res;
    };
  })();
  
  // 144. 二叉树的前序遍历
  (function () {
    // 递归法
    // var preorderTraversal = function (root) {
    //   const res = [];
    //   const dfs = root => {
    //     if (root === null) return;
    //     res.push(root.val);
    //     dfs(root.left, res);
    //     dfs(root.right, res);
    //     return res;
    //   };
    //   dfs(root);
    //   return res;
    // };
  
    // 迭代法
    var preorderTraversal = function (root, res = []) {
      if (!root) return;
      const stack = [root];
      let cur = null;
      while (stack.length) {
        cur = stack.pop();
        res.push(cur.val);
        cur.right && stack.push(cur.right);
        cur.left && stack.push(cur.left);
      }
      return res;
    };
  })();
  
  //145. 二叉树的后序遍历
  (function () {
    var postorderTraversal = function (root) {
      const res = [];
      const dfs = root => {
        if (root === null) return;
        dfs(root.left, res);
        dfs(root.right, res);
        res.push(root.val);
        return res;
      };
      dfs(root);
      return res;
    };
  
    // 迭代法
    var postorderTraversal = function (root) {
      if (!root) return;
      const [stack, res] = [[root], []];
  
      while (stack.length) {
        const cur = stack.pop();
        res.push(cur.val);
        cur.right && stack.push(cur.right);
        cur.left && stack.push(cur.left);
      }
      return res.reverse();
    };
  })();
  
  // 94. 二叉树的中序遍历
  (function () {
    var inorderTraversal = function (root) {
      const res = [];
      const dfs = root => {
        if (root === null) return;
        dfs(root.left, res);
        res.push(root.val);
        dfs(root.right, res);
        return res;
      };
      dfs(root);
      return res;
    };
  
    // 迭代法
    var inorderTraversal = function (root) {
      const [res, stack] = [[], []];
      let cur = root;
      while (cur || stack.length) {
        if (cur) {
          stack.push(cur);
          cur = cur.left;
        } else {
          cur = stack.pop();
          res.push(cur.val);
          cur = cur.right;
        }
      }
      return res;
    };
  })();
  
  // 102. 二叉树的层序遍历
  (function () {
    var levelOrder = function (root) {
      if (!root) return [];
      let [res, queue] = [[], [root]];
      while (queue.length) {
        let len = queue.length;
        let tempArr = [];
        for (let i = 0; i < len; i++) {
          let node = queue.shift();
          tempArr.push(node.val);
          node.left && queue.push(node.left);
          node.right && queue.push(node.right);
        }
        res.push(tempArr);
      }
      return res;
    };
  })();
  
  // 226.翻转二叉树
  (function () {
    var invertTree = function (root) {
      if (!root) return root;
      [root.right, root.left] = [invertTree(root.left), invertTree(root.right)];
      return root;
    };
  })();
  
  // 101. 对称二叉树
  (function () {
    var isSymmetric = function (root) {
      if (!root) return true;
  
      const dfs = (leftNode, rightNode) => {
        if ((!leftNode && rightNode) || (leftNode && !rightNode)) {
          return false;
        } else if (!leftNode && !rightNode) {
          return true;
        } else if (!Object.is(leftNode.val, rightNode.val)) {
          return false;
        }
        const outside = dfs(leftNode.left, rightNode.right);
        const inside = dfs(leftNode.right, rightNode.left);
        return outside && inside;
      };
      return dfs(root.left, root.right);
    };
  })();
  
  // 104. 二叉树的最大深度
  (function () {
    var maxDepth = function (root) {
      if (!root) return 0;
      const leftHeight = maxDepth(root.left);
      const rightHeight = maxDepth(root.right);
      return 1 + Math.max(leftHeight, rightHeight);
    };
  });
  
  // 111. 二叉树的最小深度
  (function () {
    var minDepth = function (root) {
      if (!root) return 0;
      const leftHeight = minDepth(root.left);
      const rightHeight = minDepth(root.right);
      if (!root.left && root.right) {
        return 1 + rightHeight;
      }
      if (root.left && !root.right) {
        return 1 + leftHeight;
      }
      const res = 1 + Math.min(leftHeight, rightHeight);
      return res;
    };
  })();
  
  // 222. 完全二叉树的节点个数
  (function () {
    var countNodes = function (root) {
      if (!root) return 0;
      let [left, right] = [root.left, root.right];
      let [leftDepth, rightDepth] = [0, 0];
      while (left) {
        left = left.left;
        leftDepth++;
      }
      while (right) {
        right = right.right;
        rightDepth++;
      }
      if (leftDepth === rightDepth) {
        return Math.pow(2, leftDepth + 1) - 1;
      }
      leftSum = countNodes(root.left);
      rightSum = countNodes(root.right);
      return leftSum + rightSum + 1;
    };
  })();
  
  // 110. 平衡二叉树
  (function () {
    var isBalanced = function (root) {
      const getHeight = node => {
        if (node === null) return 0;
        let leftHeight = getHeight(node.left);
        if (leftHeight === -1) return -1;
        let rightHeight = getHeight(node.right);
        if (rightHeight === -1) return -1;
        let res = 0;
        if (Math.abs(leftHeight - rightHeight) > 1) {
          return -1;
        } else {
          return Math.max(leftHeight, rightHeight) + 1;
        }
      };
      return !(getHeight(root) === -1);
    };
  })();
  
  // 257. 二叉树的所有路径
  (function () {
    var binaryTreePaths = function (root) {
      const res = [];
      const routerAll = (node, path) => {
        path.push(node.val);
        if (node.right === null && node.left === null) {
          res.push(path.join('->'));
          return;
        }
        if (node.left) {
          routerAll(node.left, path);
          path.pop();
        }
        if (node.right) {
          routerAll(node.right, path);
          path.pop();
        }
      };
      routerAll(root, []);
      return res;
    };
  })();
  
  // 404.左叶子之和
  (function () {
    var sumOfLeftLeaves = function (root) {
      if (!root) return 0;
      if (root.left === null && root.right === null) return 0;
      let leftNum = sumOfLeftLeaves(root.left);
      if (root.left !== null && root.left.right === null && root.left.left === null) {
        leftNum = root.left.val;
      }
      let rightNum = sumOfLeftLeaves(root.right);
      return rightNum + leftNum;
    };
  })();
  
  // 513. 找树左下角的值
  (function () {
    var findBottomLeftValue = function (root) {
      let res;
      let maxDepth = Math.max();
      const traversal = (node, depth) => {
        if (node.left === null && node.right === null) {
          if (depth > maxDepth) {
            maxDepth = depth;
            res = node.val;
          }
        }
        if (node.left) {
          depth++;
          traversal(node.left, depth);
          depth--;
        }
        if (node.right) {
          depth++;
          traversal(node.right, depth);
          depth--;
        }
      };
      traversal(root, 0);
      return res;
    };
  })();
  
  // 112. 路径总和
  (function () {
    var hasPathSum = function (root, targetSum) {
      if (!root) return false;
      const traversal = (node, count) => {
        if (!node.left && !node.right) return count === 0;
        if (node.left) {
          count -= node.left.val;
          if (traversal(node.left, count)) return true;
          count += node.left.val;
        }
        if (node.right) {
          count -= node.right.val;
          if (traversal(node.right, count)) return true;
          count += node.right.val;
        }
        return false;
      };
      return traversal(root, targetSum - root.val);
    };
  })();
  
  // 106. 从中序与后序遍历序列构造二叉树
  (function () {
    var buildTree = function (inorder, postorder) {
      if (!inorder.length) return null;
      const rootVal = postorder.pop();
      let rootIndex = inorder.indexOf(rootVal);
      const root = new TreeNode(rootVal);
      if (inorder.length === 1) return root;
      root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(1, rootIndex));
      root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex));
      return root;
    };
  })();
  
  // 654.最大二叉树
  (function () {
    var constructMaximumBinaryTree = function (nums) {
      const [len] = [nums.length];
      if (len === 1) return new TreeNode(nums[0]);
      const maxData = Math.max(...nums);
      const node = new TreeNode(maxData);
      const index = nums.indexOf(maxData);
      if (index > 0) {
        node.left = constructMaximumBinaryTree(nums.slice(0, index));
      }
      if (index < len - 1) {
        node.right = constructMaximumBinaryTree(nums.slice(index + 1, len));
      }
      return node;
    };
  })();
  
  // 617.合并二叉树
  (function () {
    var mergeTrees = function (root1, root2) {
      if (!root1) return root2;
      if (!root2) return root1;
      const node = new TreeNode(0);
      node.val = root1.val + root2.val;
      node.left = mergeTrees(root1.left, root2.left);
      node.right = mergeTrees(root1.right, root2.right);
      return node;
    };
  })();
  
  // 700.二叉搜索树中的搜索
  (function () {
    var searchBST = function (root, val) {
      // if (root.left === null && root.right === null) return -1;
      if (root === null || root.val === val) return root;
      let res = null;
      if (root.val < val) {
        res = searchBST(root.right, val);
      }
      if (root.val > val) {
        res = searchBST(root.left, val);
      }
      return res;
    };
  })();
  
  // 98.验证二叉搜索树  (双指针)
  (function () {
    var isValidBST = function (root) {
      let pre = null;
      const isOrder = root => {
        if (!root) return true;
        let left = isOrder(root.left);
        if (pre && root.val <= pre.val) return false;
        pre = root;
        let right = isOrder(root.right);
        return left && right;
      };
      return isOrder(root);
    };
  })();
  
  // 530.二叉搜索树的最小绝对差  (双指针)
  (function () {
    var getMinimumDifference = function (root) {
      let [pre, res] = [null, Math.min()];
      const traversal = cur => {
        if (!cur) return;
        traversal(cur.left);
        if (pre) {
          res = Math.min(res, cur.val - pre.val);
        }
        pre = cur;
        traversal(cur.right);
      };
      traversal(root);
      return res;
    };
  })();
  
  // 501.二叉搜索树中的众数
  (function () {
    var findMode = function (root) {
      let [pre, count, maxCount, res] = [null, 0, 0, []];
      const traversal = cur => {
        if (!cur) return;
        traversal(cur.left);
        if (pre === null) {
          count = 1;
        } else if (pre.val === cur.val) {
          count++;
        } else {
          count = 1;
        }
        if (count === maxCount) {
          res.push(cur.val);
        } else if (count > maxCount) {
          res = [];
          maxCount = count;
          res.push(cur.val);
        }
        pre = cur;
        traversal(cur.right);
      };
      traversal(root);
      return res;
    };
  })();
  
  // 236. 二叉树的最近公共祖先
  /**
   * 遍历的是节点，不是节点值
   */
  (function () {
    var lowestCommonAncestor = function (root, p, q) {
      const traversal = (node, p, q) => {
        if (node === null) return null;
        if (node.val === p.val || node.val === q.val) return node;
        let left = traversal(node.left, p, q);
        let right = traversal(node.right, p, q);
        if (right !== null && left !== null) {
          return node;
        }
        if (right === null && left !== null) {
          return left;
        } else if (right !== null && left === null) {
          return right;
        } else {
          return null;
        }
      };
      return traversal(root, p, q);
    };
  })();
  
  // 235. 二叉搜索树的最近公共祖先
  (function () {
    var lowestCommonAncestor = function (root, p, q) {
      let left, right;
      if (!root) return null;
      if (root.val > p.val && root.val > q.val) {
        left = lowestCommonAncestor(root.left, p, q);
        if (left) return left;
      }
      if (root.val < p.val && root.val < q.val) {
        right = lowestCommonAncestor(root.right, p, q);
        if (right) return right;
      }
      return root;
    };
  })();
  
  // 701. 二叉搜索树中的插入操作
  (function () {
    var insertIntoBST = function (root, val) {
      if (!root) {
        return new TreeNode(val);
      }
      if (root.val < val) {
        root.right = insertIntoBST(root.right, val);
      }
      if (root.val > val) {
        root.left = insertIntoBST(root.left, val);
      }
      return root;
    };
  })();
  
  // 450. 删除二叉搜索树中的节点
  (function () {
    var deleteNode = function (root, key) {
      if (!root) return null;
      if (root.val === key) {
        if (!root.left && !root.right) {
          return null;
        } else if (!root.left && root.right) {
          return root.right;
        } else if (root.left && !root.right) {
          return root.left;
        } else {
          let cur = root.right;
          while (cur.left) {
            cur = cur.left;
          }
          cur.left = root.left;
          return root.right;
        }
      }
      if (root.val < key) {
        root.right = deleteNode(root.right, key);
      }
      if (root.val > key) {
        root.left = deleteNode(root.left, key);
      }
      return root;
    };
  })();
  
  // 669. 修剪二叉搜索树
  (function () {
    function TreeNode(val, left, right) {
      this.val = val === undefined ? 0 : val;
      this.left = left === undefined ? null : left;
      this.right = right === undefined ? null : right;
    }
  
    const root = new TreeNode(3);
    root.left = new TreeNode(0);
    root.right = new TreeNode(4);
    root.left.right = new TreeNode(2);
    root.left.right.left = new TreeNode(1);
  
    var trimBST = function (root, low, high) {
      if (!root) return null;
      if (root.val < low) {
        const left = trimBST(root.right, low, high);
        return left;
      }
      if (root.val > high) {
        const right = trimBST(root.left, low, high);
        return right;
      }
      root.left = trimBST(root.left, low, high);
      root.right = trimBST(root.right, low, high);
  
      return root;
    };
  })();
  
  // 108.将有序数组转换为二叉搜索树
  (function () {
    var sortedArrayToBST = function (nums) {
      const buildTree = (nums, left, right) => {
        if (left > right) return null;
        const mid = (left + right) >> 1;
        const root = new TreeNode(nums[mid]);
        root.left = buildTree(nums, left, mid - 1);
        root.right = buildTree(nums, mid + 1, right);
        return root;
      };
      buildTree(nums, 0, nums.length - 1);
    };
  })();
  
  // 538. 把二叉搜索树转换为累加树
  (function () {
    var convertBST = function (root) {
      let pre = 0;
      const traversal = cur => {
        if (!cur) return;
        traversal(cur.right);
        cur.val += pre;
        pre = cur.val;
        traversal(cur.left);
      };
      traversal(root);
      return root;
    };
  })();
  
  // 77. 组合
  (function () {
    var combine = function (n, k) {
      const res = [];
      let path = [];
      const dfs = startIndex => {
        if (path.length === k) {
          res.push([...path]);
          return;
        }
        for (let index = startIndex; index <= n; index++) {
          path.push(index);
          dfs(index + 1);
          path.pop();
        }
      };
      dfs(1);
      return res;
    };
  })();
  
  // 77. 组合(剪枝)
  (function () {
    var combine = function (n, k) {
      const res = [];
      const path = [];
  
      const dfs = startIndex => {
        if (path.length === k) {
          res.push([...path]);
          return;
        }
  
        for (let i = startIndex; i <= n - (k - path.length) + 1; i++) {
          path.push(i);
          dfs(i + 1);
          path.pop();
        }
      };
      dfs(1);
      return res;
    };
  })();
  
  // 216.组合总和III
  (function () {
    var combinationSum3 = function (k, n) {
      const [res, path] = [[], []];
      let sum = 0;
      const dfs = startIndex => {
        if (sum > n) return;
        if (path.length === k && sum === n) {
          res.push([...path]);
          return;
        }
        for (let i = startIndex; i <= 9 - (k - path.length) + 1; i++) {
          sum += i;
          startIndex += 1;
          path.push(i);
          dfs(i);
          sum -= i;
          path.pop();
        }
      };
      dfs(1);
      return res;
    };
  })();
  
  // 17.电话号码的字母组合
  (function () {
    var letterCombinations = function (digits) {
      if (digits.length < 1) return [];
      const letterMap = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
      const res = [];
      const path = [];
      const dfs = (digits, index) => {
        if (index === digits.length) {
          res.push(path.join(''));
          return;
        }
        const num = digits[index] - 0;
        let now = letterMap[num];
        for (let i = 0; i < now.length; i++) {
          path.push(now[i]);
          dfs(digits, index + 1);
          path.pop();
        }
      };
      dfs(digits, 0);
      return res;
    };
  })();
  
  // 39. 组合总和
  (function () {
    var combinationSum = function (candidates, target) {
      const res = [];
      let path = [];
      const dfs = (startIndex, sum) => {
        if (sum === target) {
          res.push([...path]);
          return;
        } else if (sum > target) {
          return;
        }
        for (let i = startIndex; i < candidates.length; i++) {
          path.push(candidates[i]);
          sum += candidates[i];
          dfs(i, sum);
          sum -= candidates[i];
          path.pop();
        }
      };
      dfs(0, 0);
      return res;
    };
  })();
  
  // 40. 组合总和 II
  (function () {
    var combinationSum2 = function (candidates, target) {
      const [res, path, len] = [[], [], candidates.length];
      const used = Array(len).fill(0);
      candidates.sort((a, b) => a - b);
  
      const dfs = (startIndex, sum, used) => {
        if (sum > target) return;
        if (sum === target) {
          res.push([...path]);
          return;
        }
  
        for (let i = startIndex; i < len; i++) {
          if (i > 0 && candidates[i] === candidates[i - 1] && used[i - 1] === 0) {
            continue;
          }
          used[i] = 1;
          sum += candidates[i];
          path.push(candidates[i]);
          dfs(i + 1, sum, used);
          used[i] = 0;
          sum -= candidates[i];
          path.pop();
        }
      };
      dfs(0, 0, used);
      return res;
    };
  })();
  
  // 131. 分割回文串
  (function () {
    var partition = function (s) {
      const [res, len] = [[], s.length];
      const isPalindrome = (startIndex, i) => {
        while (startIndex <= i) {
          if (s[startIndex] === s[i]) {
            startIndex++;
            i--;
          } else {
            return false;
          }
        }
        return true;
      };
  
      const dfs = (path, startIndex) => {
        if (startIndex >= len) {
          res.push([...path]);
          return;
        }
        for (let i = startIndex; i < len; i++) {
          if (!isPalindrome(startIndex, i)) continue;
          path.push(s.slice(startIndex, i + 1));
          dfs(path, i + 1);
          path.pop();
        }
      };
      dfs([], 0);
      return res;
    };
  })();
  
  // 93. 复原 IP 地址
  (function () {
    var restoreIpAddresses = function (s) {
      const res = [];
      const dfs = (startIndex, path) => {
        if (path.length > 4) return;
        if (path.length === 4 && startIndex === s.length) {
          res.push(path.join('.'));
          return;
        }
        for (let i = startIndex; i < s.length; i++) {
          const str = s.slice(startIndex, i + 1);
          if (str.length > 3 || +str > 255) break;
          if (str.length > 1 && str[0] === '0') break;
          path.push(str);
          dfs(i + 1, path);
          path.pop();
        }
      };
      dfs(0, []);
      return res;
    };
  })();
  
  // 78. 子集
  (function () {
    var subsets = function (nums) {
      const [res, len] = [[], nums.length];
      const dfs = (startIndex, path) => {
        res.push([...path]);
        if (startIndex >= len) return;
        for (let i = startIndex; i < len; i++) {
          path.push(nums[i]);
          dfs(i + 1, path);
          path.pop();
        }
      };
      dfs(0, []);
      return res;
    };
  })();
  
  // 90. 子集 II
  (function () {
    var subsetsWithDup = function (nums) {
      const [res, len] = [[], nums.length];
      nums.sort((a, b) => a - b);
      const used = Array(len).fill(0);
      const dfs = (startIndex, path) => {
        res.push([...path]);
        if (startIndex > len) return;
        for (let i = startIndex; i < len; i++) {
          if (i > 0 && nums[i] === nums[i - 1] && used[i - 1] === 0) continue;
          path.push(nums[i]);
          used[i] = 1;
          dfs(i + 1, path);
          path.pop();
          used[i] = 0;
        }
      };
      dfs(0, []);
      return res;
    };
  })();
  
  // 491. 递增子序列
  (function () {
    var findSubsequences = function (nums) {
      const [res, len] = [[], nums.length];
      const dfs = (startIndex, path) => {
        const len2 = path.length;
        if (len2 > 1) res.push([...path]);
        const usedSet = new Set();
        for (let i = startIndex; i < len; i++) {
          if ((path && nums[i] < path[len2 - 1]) || usedSet.has(nums[i])) continue;
          usedSet.add(nums[i]);
          path.push(nums[i]);
          dfs(i + 1, path);
          path.pop();
        }
      };
      dfs(0, []);
      return res;
    };
  })();
  
  // 46. 全排列
  (function () {
    var permute = function (nums) {
      const [res, len] = [[], nums.length];
      const used = Array(len).fill(0);
      const dfs = path => {
        if (path.length === len) {
          res.push([...path]);
          return;
        }
        for (let i = 0; i < len; i++) {
          if (used[i] !== 0) continue;
          used[i] = 1;
          path.push(nums[i]);
          dfs(path);
          used[i] = 0;
          path.pop();
        }
      };
      dfs([]);
      return res;
    };
  })();
  
  // 47. 全排列 II
  (function () {
    var permuteUnique = function (nums) {
      const [res, len] = [[], nums.length];
      const used = Array(len).fill(0);
      nums.sort((a, b) => a - b);
      const dfs = path => {
        if (path.length === len) {
          res.push([...path]);
          return;
        }
        for (let i = 0; i < len; i++) {
          if ((i > 0 && nums[i] === nums[i - 1] && used[i - 1] === 0) || used[i] === 1) continue;
          used[i] = 1;
          path.push(nums[i]);
          dfs(path);
          used[i] = 0;
          path.pop();
        }
      };
      dfs([]);
      return res;
    };
  })();
  
  // 51. N皇后
  (function () {
    const isValid = (board, row, col, n) => {
      for (let i = 0; i < row; i++) {
        if (board[i][col] === 'Q') {
          return false;
        }
      }
  
      for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] === 'Q') {
          return false;
        }
      }
  
      for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] === 'Q') {
          return false;
        }
      }
      return true;
    };
    const transformChessBoard = chessBoard => {
      const res = [];
      chessBoard.forEach(row => {
        let rowStr = '';
        row.forEach(value => (rowStr += value));
        res.push(rowStr);
      });
      return res;
    };
    var solveNQueens = function (n) {
      const res = [];
      const board = Array.from(new Array(n), () => new Array(n).fill('.'));
      const dfs = (board, row) => {
        if (row === n) {
          res.push(transformChessBoard(board));
          return;
        }
        for (let i = 0; i < n; i++) {
          if (isValid(board, row, i, n)) {
            board[row][i] = 'Q';
  
            dfs(board, row + 1);
            board[row][i] = '.';
          }
        }
      };
      dfs(board, 0);
      return res;
    };
  })();
  
  // 37. 解数独
  (function () {
    const isValid = (row, col, val, board) => {
      let len = board.length;
      // 行不能重复
      for (let i = 0; i < len; i++) {
        if (board[row][i] === val) {
          return false;
        }
      }
      // 列不能重复
      for (let i = 0; i < len; i++) {
        if (board[i][col] === val) {
          return false;
        }
      }
      let startRow = Math.floor(row / 3) * 3;
      let startCol = Math.floor(col / 3) * 3;
  
      for (let i = startRow; i < startRow + 3; i++) {
        for (let j = startCol; j < startCol + 3; j++) {
          if (board[i][j] === val) {
            return false;
          }
        }
      }
  
      return true;
    };
    var solveSudoku = function (board) {
      const dfs = board => {
        for (let row = 0; row < board.length; row++) {
          for (let col = 0; col < board[0].length; col++) {
            if (board[row][col] === '.') {
              for (let i = 1; i <= 9; i++) {
                if (isValid(row, col, `${i}`, board)) {
                  board[row][col] = `${i}`;
                  const res = dfs(board);
                  if (res) return true;
                  board[row][col] = '.';
                }
              }
              return false;
            }
          }
        }
        return true;
      };
      dfs(board);
      return board;
    };
  })();
  
  // 455.分发饼干
  (function () {
    // 优先满足胃口大的
    var findContentChildren = function (g, s) {
      g.sort((a, b) => a - b);
      s.sort((a, b) => a - b);
      let [res, index] = [0, s.length - 1];
  
      for (let i = g.length - 1; i >= 0; i--) {
        if (index >= 0 && s[index] >= g[i]) {
          res++;
          index--;
        }
      }
      return res;
    };
  
    // 优先满足胃口小的
    var findContentChildren = function (g, s) {
      g.sort((a, b) => a - b);
      s.sort((a, b) => a - b);
      let [res, index] = [0, 0];
      for (let i = 0; i < s.length; i++) {
        if (s[i] >= g[index]) {
          res++;
          index++;
        }
      }
      return res;
    };
  })();
  
  // 376. 摆动序列
  (function () {
    var wiggleMaxLength = function (nums) {
      const len = nums.length;
      if (len === 1) return 1;
      let [preDiff, curDiff, res] = [0, 0, 1];
      for (let i = 0; i < len - 1; i++) {
        curDiff = nums[i] - nums[i + 1];
        if ((preDiff >= 0 && curDiff < 0) || (preDiff <= 0 && curDiff > 0)) {
          res++;
          preDiff = curDiff;
        }
      }
      return res;
    };
  })();
  
  // 53. 最大子序和
  (function () {
    var maxSubArray = function (nums) {
      let [res, len, sum] = [Math.max(), nums.length, 0];
      for (let i = 0; i < len; i++) {
        sum += nums[i];
        res = Math.max(sum, res);
        if (sum < 0) {
          sum = 0;
        }
      }
      return res;
    };
  })();
  
  // 122.买卖股票的最佳时机II
  (function () {
    var maxProfit = function (prices) {
      let res = 0;
      for (let i = 1; i < prices.length; i++) {
        res += Math.max(prices[i] - prices[i - 1], 0);
      }
      return res;
    };
  })();
  
  // 55. 跳跃游戏
  (function () {
    var canJump = function (nums) {
      let [cover, len] = [0, nums.length - 1];
      if (len === 0) return true;
      for (let i = 0; i <= cover; i++) {
        cover = Math.max(cover, i + nums[i]);
        if (cover === len) return true;
      }
      return false;
    };
  })();
  
  // 45. 跳跃游戏 II
  (function () {
    var jump = function (nums) {
      let [cur, next, len, res] = [0, 0, nums.length - 1, 0];
      if (len === 0) return 0;
      for (let i = 0; i < len; i++) {
        next = Math.max(next, i + nums[i]);
        if (i === cur) {
          if (cur !== len) {
            res++;
            cur = next;
            if (cur >= len) break;
          } else {
            break;
          }
        }
      }
      return res;
    };
  })();
  
  // 1005.K次取反后最大化的数组和
  (function () {
    var largestSumAfterKNegations = function (nums, k) {
      const len = nums.length;
      let sum = 0;
      nums.sort((a, b) => Math.abs(b) - Math.abs(a));
      for (let i = 0; i < len; i++) {
        if (k > 0 && nums[i] < 0) {
          nums[i] *= -1;
          k--;
        }
        if (i !== len - 1) {
          sum += nums[i];
        }
      }
      if ((k & 1) === 1) {
        nums[len - 1] *= -1;
      }
  
      sum += nums[len - 1];
      return sum;
    };
  })();
  
  // 134. 加油站
  (function () {
    var canCompleteCircuit = function (gas, cost) {
      let [start, curSum, totalSum, len] = [0, 0, 0, gas.length];
      for (let i = 0; i < len; i++) {
        curSum += gas[i] - cost[i];
        totalSum += gas[i] - cost[i];
        if (curSum < 0) {
          start = i + 1;
          curSum = 0;
        }
      }
      if (totalSum < 0) return -1;
      return start;
    };
  })();
  
  // 135. 分发糖果
  (function () {
    var candy = function (ratings) {
      const len = ratings.length;
      const candys = new Array(len).fill(1);
      for (let i = 1; i < len; i++) {
        if (ratings[i] > ratings[i - 1]) {
          candys[i] = candys[i - 1] + 1;
        }
      }
      for (let i = len - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
          candys[i] = Math.max(candys[i], candys[i + 1] + 1);
        }
      }
      return candys.reduce((pre, cur) => pre + cur, 0);
    };
  })();
  
  // 860.柠檬水找零
  (function () {
    var lemonadeChange = function (bills) {
      let [five, ten, twenty, len] = [0, 0, 0, bills.length];
      for (let i = 0; i < len; i++) {
        if (bills[i] === 5) {
          five++;
        } else if (bills[i] === 10 && five > 0) {
          five--;
          ten++;
        } else if (bills[i] === 20) {
          if (five > 0 && ten > 0) {
            twenty++;
            five--;
            ten--;
          } else if (five >= 3) {
            five -= 3;
          } else {
            return false;
          }
        } else {
          return false;
        }
      }
      return true;
    };
  })();
  
    </textarea>
  </div>
</body>

</html>